package queue;

import linearList.Node;

/**
 * 链表存储队列
 * @param <T>
 */
public class LinkedQueue<T> implements Queue<T> {
    private Node<T> front, rear;
    public LinkedQueue() {
        this.front = this.rear = null;
    }

    @Override
    public String toString() {
        StringBuffer ret = new StringBuffer("(");
        for (Node<T> p = this.front;p != null;p = p.next) {
            ret.append(p.data + ",");
        }

        if (ret.length() > 1) {
            ret.deleteCharAt(ret.length() - 1);
        }
        ret.append(")");
        return ret.toString();
    }

    @Override
    public boolean isEmpty() {
        return this.front == null && this.rear == null;
    }

    @Override
    public boolean add(T x) {
        if (x == null) {
            return false;
        }
        Node<T> q = new Node<T>(x,null);

//        插入节点
        if (this.front == null) {
            this.front = q;
        } else {
            this.rear.next = q;
        }

//        设置尾指针
        this.rear = q;
        return true;
    }

    @Override
    public T peek() {
        return this.isEmpty() ? null : this.front.data;
    }

    @Override
    public T poll() {
        if (isEmpty()) {
            return null;
        }
        T x = this.front.data;
        this.front = this.front.next;

//        队列为空的情况
        if (this.front == null) {
            this.rear = null;
        }
        return x;
    }

    public static void main(String args[])
    {
        LinkedQueue<Integer> q = new LinkedQueue<Integer>();
        q.add(new Integer(9));
        q.add(new Integer(18));
        System.out.println("poll : "+q.poll().toString()+"  "+q.poll().toString()+"   ");
        System.out.println(q.toString());
        q.add(new Integer(80));
        q.add(new Integer(50));
        q.add(new Integer(50));
        q.add(new Integer(60));
        System.out.println(q.toString());
        q.add(new Integer(70));
        System.out.println(q.toString());
    }

}
